package com.github.tangmonkmeat;

import sun.java2d.pipe.SpanClipRenderer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/16 上午8:06
 */
public class 最长上升子数组的长度 {

    public static void main(String[] args) {

        int[] nums = new int[]{1,3,6,7,9,4,10,5,6};

        int length = lengthOfLIS(nums);

        System.out.println(length);
    }

    public static int lengthOfLIS(int[] nums) {
        if(nums.length <= 1){
            return 1;
        }
        // 以第 i 个元素为最后一个的最长递增子序列
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int currMax = 1;
        for(int i = 1;i < dp.length;i++){
            // 自己就是一个
            dp[i] = 1;
            // 查找当前元素前的最长递增子序列
            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            currMax = Math.max(currMax, dp[i]);
        }
        return currMax;
    }
}
